package com.my.study.structures.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author Carlos
 * @version 1.0
 * @Description 快速排序
 * <p>
 * 基本思想：它是对冒泡排序的一种改进，
 * <p>
 * 在一组无序集合中，选取一个基准数，根据这个基准数把无序集合分为了三部分，左边部分的集合中的数小于基准数，
 * 右边部分的集合中的数大于基准数；
 * <p>
 * 使用递归把左右无序集合继续分组，直到不能分为止，再合并
 * @date 2021/7/20 22:23
 **/
public class QuickSort {


    public static void main(String[] args) {
        int[] arr = {1, -9, 78, 0, 23, -567, 70, 0};

//        sort(arr, 0, arr.length - 1);

        sort01(arr, 0, arr.length - 1);

        // [-9, -567, 0, 23, 78, 70]
        System.out.println(Arrays.toString(arr));

    }


    private static void sort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int pivot = (right + left) / 2;
        int pivotVal = arr[pivot];


        // 让比pivotVal值小的放在左集合，大的放在右集合
        while (l < r) {
            //左 -> 找到大于等于pivotVal的值
            while (arr[l] < pivotVal) {
                l++;
            }
            //右 -> 找到小于等于pivotVal的值
            while (arr[r] > pivotVal) {
                r--;
            }
            // 表明：左边集合都小于等于pivotVal；右边集合都大于等于pivotVal
            if (l >= r) {
                break;
            }

            // 需要交换
            swap(arr, l, r);

            // 如果交换后，发现这个arr[l] == pivotVal，则r--
            if (arr[l] == pivotVal) {
                r--;
            }
            // 如果交换后，发现这个arr[r] == pivotVal，则l++
            if (arr[r] == pivotVal) {
                l++;
            }
        }

        if (l == r) {
            r--;
            l++;
        }

        if (left < r) {
            sort(arr, left, r);
        }

        if (right > l) {
            sort(arr, l, right);
        }
    }


    private static void sort01(int[] arr, int left, int right) {
        if (left >= right) return;

        int leftRow = left;
        // 哨兵
        int rightRow = right;

        int random = new Random().nextInt(right - left) + left;
        swap(arr, random, right);

        while (left < right) {

            while (arr[left] < arr[rightRow] && left < right) {
                left++;
            }

            while (arr[right] >= arr[rightRow] && left < right) {
                right--;
            }

            if (left == right) {
                swap(arr, left, rightRow);
            } else {
                swap(arr, left, right);
            }
        }

        sort01(arr, leftRow, left - 1);
        sort01(arr, right + 1, rightRow);
    }

    private static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }


    private static void sort2(int[] a, int left, int right) {
        if (left < right) {
            int l, r, pivot;
            l = left;
            r = right;
            pivot = a[l];

            while (l < r) {
                while (a[r] > pivot && l < r) {
                    r--;
                }
                if (l < r) {
                    a[l++] = a[r];
                }
                while (a[l] < pivot && l < r) {
                    l++;
                }
                if (l < r) {
                    a[r--] = a[l];
                }
            }
            a[l] = pivot;

            sort2(a, left, l - 1);
            sort2(a, l + 1, right);
        }
    }

}
